package org.getOffer.offer47;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;

/**
 * @Author yu
 * @Date 2021/10/17
 */
public class Solution {

    public static void main(String[] args) {

        int[][] ints = {{1,3,1}, {1,5,1}, {4,2,1}};

        Solution solution = new Solution();
        System.out.println(solution.maxValue(ints));

    }

//    int max = 0;
//
//    public int maxValue(int[][] grid) {
//
//        int sum = 0;
//
//        this.recursion(0, 0, grid, sum);
//
//        return max;
//    }
//
//    public void recursion(int line, int row, int[][] grid, int sum) {
//
//        if (line == grid.length && row == grid[0].length) {
//            return;
//        }
//
//        if (line < grid.length && row < grid[0].length) {
//            sum += grid[line][row];
//            this.recursion(line+1, row, grid, sum);
//            this.recursion(line, row+1, grid, sum);
//        }
//
//        max = Math.max(max, sum);
//
//        //list.add(sum);
//
//    }

    public int maxValue(int[][] grid) {

        for (int i = 0; i < grid.length; i++) {
            for (int j= 0; j < grid[0].length; j++) {
                if (j != 0 && i == 0) {
                    grid[i][j] += grid[i][j-1];
                }
                if (i != 0 && j == 0) {
                    grid[i][j] += grid[i-1][j];
                }
                if (j != 0 && i != 0) {
                    grid[i][j] += Math.max(grid[i][j-1], grid[i-1][j]);
                }
            }
        }

        return grid[grid.length-1][grid[0].length-1];

    }

}
